import java.util.*;

public class ComputeSimilarities {
  
  // public List<String> computeSimilarities(int[][] docs) {
  //     List<String> res = new ArrayList<>();
  //     for (int i = 0; i < docs.length; i++) { 
  //       for(int j = i + 1; j < docs.length; j++){
  //         double sim = computeSimilarity(docs[i], docs[j]);
  //         if (sim > 0) {
  //           res.add(i + "," + j + ": " + String.format("%.4f", sim));
  //         }
  //       }
  //     }
  //     return res;
  // }

  // private double computeSimilarity(int[] doc1, int[] doc2) {
  //   int i = 0, j = 0;
  //   Arrays.sort(doc1);
  //   Arrays.sort(doc2);
  //   int count = 0;
  //   while (i < doc1.length && j < doc2.length) {
  //     if (doc1[i] == doc2[j]) {
  //       i++;
  //       j++;
  //       count++;
  //     } else if (doc1[i] < doc2[j]) {
  //       i++;
  //     } else {
  //       j++;
  //     }
  //   }
  //   return count * 1.0 / (doc1.length + doc2.length - count);
  // }

  // hash map 解法

  static class Pair {
    int first;
    int second;
  
    Pair(int first, int second) {
      if (first > second) {
        this.first = second;
        this.second = first;
      } else {
        this.first = first;
        this.second = second;
      }
    }
  
    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (!(o instanceof Pair)) return false;
      Pair pair = (Pair) o;
      return first == pair.first && second == pair.second;
    }
  
    @Override
    public int hashCode() {
      return Objects.hash(first, second);
    }
  }
  public List<String> computeSimilarities(int[][] docs) {
    List<String> res = new ArrayList<>();
    Map<Integer, Set<Integer>> map = new HashMap<>();
    for(int index = 0; index < docs.length; index++){
      int[] doc = docs[index];
      for(int i = 0; i < doc.length; i++){
        Set<Integer> set = map.getOrDefault(doc[i], new HashSet<>());
        set.add(index);
        map.put(doc[i], set);
      }
    }

    Map<Pair, Integer> cnt = new HashMap<>();
    for(int key: map.keySet()){
      Set<Integer> set = map.get(key);
      if(set.size() < 2){
        continue;
      }
      List<Integer> list = new ArrayList<>(set); // Convert Set to List
      for(int i = 0; i < list.size(); i++){ 
        for(int j = i + 1; j < list.size(); j++){
          int index1 = list.get(i);
          int index2 = list.get(j);
          Pair pair = new Pair(index1, index2);
          cnt.put(pair, cnt.getOrDefault(pair, 0) + 1);
        }
      }
    }

    for(Pair pair: cnt.keySet()){
      int index1 = pair.first;
      int index2 = pair.second;
      int count = cnt.get(pair);
      double sim = count * 1.0 / (docs[index1].length + docs[index2].length - count);
      res.add(index1 + "," + index2 + ": " + String.format("%.4f", sim));
    }

    return res;
  }

  public static void main(String[] args) {
    int[][] docs = {{1, 2, 3}, {2, 3, 4}, {3, 4, 5}};
    ComputeSimilarities cs = new ComputeSimilarities();
    List<String> res = cs.computeSimilarities(docs);
    System.out.println(res);
  }

}
